import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:  二叉树
 * User:岁亮亮
 * Date:2024-02-03
 * TIME:9:20
 */
public class BinaryTree2 {

    static class TreeNode{
        public char val;;
        public TreeNode  left;
        public TreeNode  right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public static int i;
    TreeNode creat(String str){
        TreeNode root=null;
        if(str.charAt(i)!='#'){
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=creat(str);
            root.right=creat(str);
        }
        else {
            i++;
        }
        return root;
    }
    TreeNode creat2() {
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        TreeNode Q=new TreeNode('Q');
        TreeNode W=new TreeNode('W');

        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        E.right=H;
        H.left=Q;
        C.left=F;
        C.right=G;
        return A;

    }

    //前序遍历
    void preOder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOder(root.left);
        preOder(root.right);
    }
    //前序非递归遍历
    void preOderNor(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                System.out.print(cur.val+" ");
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }
    }

    //中序遍历
    void inOder(TreeNode root){
        if(root==null){
            return;
        }
        inOder(root.left);
        System.out.print(root.val+" ");
        inOder(root.right);
    }
    //中序非递归遍历
    void inOderNor(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            System.out.print(top.val+" ");
            cur=top.right;
        }
    }
    //后序遍历
    void outOder(TreeNode root){
        if(root==null){
            return;
        }
        outOder(root.left);
        outOder(root.right);
        System.out.print(root.val+" ");
    }
    //后序非递归遍历
    void outOderNor(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.peek();
            if(top.right==null || top.right==prev){
                System.out.print(top.val+" ");
                stack.pop();
                prev=top;
            }
            else {
                cur=top.right;
            }
        }

    }

    //树的结点
    public int treeCount;
    int getTreeNodeCount1(TreeNode root){
        if(root==null){
            return 0;
        }
        treeCount++;
        getTreeNodeCount1(root.left);
        getTreeNodeCount1(root.right);
        return treeCount;
    }
    int getTreeNodeCount2(TreeNode root){
        if (root==null){
            return 0;
        }
        return getTreeNodeCount2(root.left)+getTreeNodeCount2(root.right)+1;
    }

    //叶子结点
    public int leafCount;
    int getLeafNodeCount1(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            leafCount++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
        return leafCount;
    }
    int getLeafNodeCount2(TreeNode root){
        if (root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }
    //树的层次
    public int floorCount;
    int getFloorCount (TreeNode root){
        /*if(root==null){
            return 0;
        }
        int count1 =0;
        int count2=0;
        if(root.left!=null||root.right!=null){
            count1=1+getFloorCount(root.left);
        }
        if(root.left!=null||root.right!=null){
            count2=1+getFloorCount(root.right);
        }
        return Math.max(count1, count2)+1;*/

        if(root==null){
            return 0;
        }
        int leftHight=getFloorCount(root.left);
        int rightHight=getFloorCount(root.right);
        return Math.max(leftHight,rightHight)+1;


    }

    //树的层数的结点
    int getfloorNodeCount(TreeNode root,int k){
        if(root==null){
            return 0;
        }
        if(k==1|| root ==null){
            return 1;
        }
        return getfloorNodeCount(root.left,k-1)+getfloorNodeCount(root.right,k-1);
    }
    //查val是否存在
    TreeNode find(TreeNode root,char val){
        if(root==null){
            return null;
        }
        if(root.val==val) {
            return root;
        }
       TreeNode leftRet= find(root.left,val);
        if(leftRet!=null){
            return leftRet;
        }
        TreeNode rightRet= find(root.right,val);
        if(rightRet!=null){
            return rightRet;
        }
        return null;
    }
    //判断俩树是否相同
    public boolean IsSameTree(TreeNode root1,TreeNode root2){
        if((root1==null&&root2!=null)||(root1!=null&&root2==null)){
            return false;
        }
        //上述代码执行完后要么都为空  要么都不为空
        if(root1==null&&root2==null){
            return true;
        }
        if(root1.val!=root2.val){
            return false;
        }
        return IsSameTree(root1.left,root2.left)&&IsSameTree(root1.right,root2.right);
    }
    //判断是否是子树
    public boolean IsSubTree(TreeNode root,TreeNode subroot){
        if(root==null||subroot==null){
            return false;
        }
        if(IsSameTree(root,subroot)){
            return true;
        }
        if(IsSubTree(root.left,subroot)){
            return true;
        }
        if(IsSubTree(root.right,subroot)){
            return true;
        }
        return false;
    }
    //翻转二叉树
    TreeNode fanzhuan(TreeNode root){
        if (root==null){
            return null;
        }
        if(root.left==null&&root.right==null){
            return root;
        }
        TreeNode ret=root.left;
        root.left=root.right;
        root.right=ret;
        fanzhuan(root.left);
        fanzhuan(root.right);
        return root;
    }
    //对称二叉树
    public boolean Isduicheng(TreeNode root){
        if(root==null){
            return true;
        }
        return IssameLeftRight(root.left,root.right);
    }
    public boolean IssameLeftRight(TreeNode leftTree,TreeNode rightTree){
        if((leftTree==null&&rightTree!=null)||(leftTree!=null&&rightTree==null)){
            return false;
        }
        if(leftTree==null&&rightTree==null){
            return true;
        }
        if(leftTree.val!=rightTree.val){
            return false;
        }
        return IssameLeftRight(leftTree.left,rightTree.right)&&IssameLeftRight(leftTree.right,rightTree.left);
    }
    //平衡二叉树
    //时间复杂度n的平方
    public boolean pinghen1(TreeNode root){
        if(root==null){
            return true;
        }
        int leftHight=getFloorCount(root.left);
        int rightHight=getFloorCount(root.right);
        return Math.abs(leftHight-rightHight)<=1&&pinghen1(root.left)&&pinghen1(root.right);
     }
     public boolean pinghen2(TreeNode root){
        if(root==null){
            return true;
        }
        return getFloorCountTopinghen(root)>=0;

     }
     public int getFloorCountTopinghen(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHight=getFloorCountTopinghen(root.left);
        int rightHight=getFloorCountTopinghen(root.right);
        if(leftHight>=0&&rightHight>=0&&Math.abs(leftHight-rightHight)<=1){
            return Math.max(leftHight,rightHight)+1;
        }
        else {
            return -1;
        }
     }
     //公共祖先
    public TreeNode ancestor(TreeNode root,TreeNode p,TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        //root的同一侧
        TreeNode leftTree=ancestor(root.left,p,q);
        TreeNode rightTree=ancestor(root.right,p,q);


        /*if(leftTree!=null){
            if(rightTree!=null){
                return root;
            }
            else {
                return leftTree;
            }
        }
        else {
           return rightTree;
        }*/

        //或者这样写循环语句
        if(leftTree!=null&&rightTree!=null){
            return root;
        }
        else if(leftTree!=null){
            return leftTree;
        }
        else {
            return rightTree;
        }
    }
    //层序遍历
    public void cengOder(TreeNode root){
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            return;
        }
        System.out.print(root.val);
        cengOder(root.left);
        cengOder(root.right);
    }

}
